package breakthrough;

import java.util.*;
import game.*;

public class AlphaBetaBreakthroughPlayer extends GamePlayer
{
	public final int MAX_DEPTH = 100;
	public final int MAX_SCORE = 1000;
	public double timeRemaining = 420000;
	public int depthLimit;

	protected ScoredBreakthroughMove[] mvStack;

	protected class ScoredBreakthroughMove extends BreakthroughMove
	{
		public ScoredBreakthroughMove(int oldRow, int oldCol, int newRow, int newCol, double s)
		{
			super(oldRow, oldCol, newRow, newCol);
			score = s;
		}

		public void set(int oldRow, int oldCol, int newRow, int newCol, double s)
		{
			startRow = oldRow;
			endingRow = newRow;
			startCol = oldCol;
			endingCol = newCol;
			score = s;
		}

		public double score;
	}

	public void init()
	{
		mvStack = new ScoredBreakthroughMove[MAX_DEPTH];
		for (int i = 0; i < MAX_DEPTH; i++)
		{
			mvStack[i] = new ScoredBreakthroughMove(0, 0, 0, 0, 0);
		}
	}

	/**
	 * Determines if the game is over (someone won)
	 * 
	 * @param brd
	 *            -- current board configuration
	 * @param mv
	 *            -- current move
	 * @return isTerminal -- true = game over, false = game continues
	 */
	protected boolean terminalValue(GameState brd, ScoredBreakthroughMove mv)
	{
		GameState.Status status = brd.getStatus();
		boolean isTerminal = true;

		if (status == GameState.Status.HOME_WIN)
		{
			mv.set(0, 0, 0, 0, MAX_SCORE);
		} else if (status == GameState.Status.AWAY_WIN)
		{
			mv.set(0, 0, 0, 0, -MAX_SCORE);
		} else
		{
			isTerminal = false;
		}
		return isTerminal;
	}

	/**
	 * Looks at the board to find which side has more pieces (and the advantage)
	 * 
	 * @param brd
	 *            -- current state of the board
	 * @return homePieces - awayPieces -- the advantage home has
	 */
	public static int evalBoard(BreakthroughState brd)
	{

		int homePieces = 0;
		int awayPieces = 0;

		char curSpace = ' '; // the current spot on the board

		for (int r = 0; r < BreakthroughState.N; r++)
		{
			for (int c = 0; c < BreakthroughState.N; c++)
			{
				curSpace = brd.board[r][c];

				if (curSpace == BreakthroughState.homeSym)
				{
					homePieces++;

				}

				else if (curSpace == BreakthroughState.awaySym)
				{
					awayPieces++;
				}
			}
		}

		return homePieces - awayPieces;
	}

	public AlphaBetaBreakthroughPlayer(String nname, int d)
	{
		super(nname, new BreakthroughState(), false);
		depthLimit = d;
		init();
	}

	/**
	 * Performs alpha beta pruning.
	 * 
	 * @param brd
	 *            -- current board state
	 * @param currDepth
	 *            -- depth search is at
	 * @param alpha
	 *            -- home evaluation score
	 * @param beta
	 *            -- away evaluation score
	 */
	private void alphaBeta(BreakthroughState brd, int currDepth, double alpha, double beta)
	{
		boolean toMaximize = (brd.getWho() == GameState.Who.HOME);
		boolean toMinimize = !toMaximize;

		boolean isTerminal = terminalValue(brd, mvStack[currDepth]);

		if (isTerminal)
		{
			; // backs out of search
		} else if (currDepth == depthLimit)
		{
			mvStack[currDepth].set(0, 0, 0, 0, evalBoard(brd));
		} else
		{
			ScoredBreakthroughMove tempMv = new ScoredBreakthroughMove(0, 0, 0, 0, 0);

			double bestScore = (toMaximize ? Double.NEGATIVE_INFINITY : Double.POSITIVE_INFINITY);
			ScoredBreakthroughMove bestMove = mvStack[currDepth];
			ScoredBreakthroughMove nextMove = mvStack[currDepth + 1];

			bestMove.set(0, 0, 0, 0, bestScore);
			GameState.Who currTurn = brd.getWho();

			char mySym = currTurn == GameState.Who.HOME ? BreakthroughState.homeSym : BreakthroughState.awaySym;
			char theirSym = currTurn == GameState.Who.HOME ? BreakthroughState.awaySym : BreakthroughState.homeSym;
			int dir = currTurn == GameState.Who.HOME ? +1 : -1;
			int oneAway = currTurn == GameState.Who.HOME ? BreakthroughState.N - 2 : 1;
			boolean gonnaWin = false;

			ArrayList<BreakthroughMove> validMoves = new ArrayList<BreakthroughMove>();

			// Looks for piece one move away from winning. 
			// If found stops the search for other moves.
			for (int c = 0; c < BreakthroughState.N; c++)
			{
				if (brd.board[oneAway][c] == mySym)
				{
					// Directly in front
					if (brd.board[oneAway + dir][c] == BreakthroughState.emptySym)
					{
						validMoves.add(new BreakthroughMove(oneAway, c, oneAway + dir, c));
					}
					// Left
					if (c != 0
							&& (brd.board[oneAway + dir][c - 1] == BreakthroughState.emptySym || brd.board[oneAway + dir][c - 1] == theirSym))
					{
						validMoves.add(new BreakthroughMove(oneAway, c, oneAway + dir, c - 1));
					}
					// Right
					if (c != BreakthroughState.N - 1
							&& (brd.board[oneAway + dir][c + 1] == BreakthroughState.emptySym || brd.board[oneAway + dir][c + 1] == theirSym))
					{
						validMoves.add(new BreakthroughMove(oneAway, c, oneAway + dir, c + 1));
					}
					if (validMoves.size() > 0)
					{
						gonnaWin = true;
					}
				}
			}

			// Looks at all possible moves if there isn't a piece about to win
			for (int r = 0; r < BreakthroughState.N && !gonnaWin; r++)
			{
				for (int c = 0; c < BreakthroughState.N && !gonnaWin; c++)
				{

					if (brd.board[r][c] == mySym)
					{

						// Directly in front

						if (brd.board[r + dir][c] == BreakthroughState.emptySym)
						{
							validMoves.add(new BreakthroughMove(r, c, r + dir, c));

						}
						// Left
						if (c != 0
								&& (brd.board[r + dir][c - 1] == BreakthroughState.emptySym || brd.board[r + dir][c - 1] == theirSym))
						{
							validMoves.add(new BreakthroughMove(r, c, r + dir, c - 1));
						}
						// Right
						if (c != BreakthroughState.N - 1
								&& (brd.board[r + dir][c + 1] == BreakthroughState.emptySym || brd.board[r + dir][c + 1] == theirSym))
						{
							validMoves.add(new BreakthroughMove(r, c, r + dir, c + 1));

						}
					}
				}
			}

			Collections.shuffle(validMoves); // shuffles the arrayList
			for (int i = 0; i < validMoves.size(); i++)
			{
				BreakthroughMove selected = validMoves.get(i);

				int sr = selected.startRow;
				int sc = selected.startCol;
				int er = selected.endingRow;
				int ec = selected.endingCol;

				// keeps track of whether or not a piece was taken in this move
				boolean tookPiece = false;
				if (brd.board[er][ec] == theirSym)
					tookPiece = true;

				// initialize move
				tempMv.startRow = sr; // sets tempMv equal to the move from the
										// arrayList
				tempMv.startCol = sc;
				tempMv.endingRow = er;
				tempMv.endingCol = ec;

				brd.makeMove(tempMv);

				alphaBeta(brd, currDepth + 1, alpha, beta); // Check out move

				// Undo move
				brd.board[sr][sc] = mySym;
				if (tookPiece)
					brd.board[er][ec] = theirSym;
				else
					brd.board[er][ec] = BreakthroughState.emptySym;
				brd.numMoves--;
				brd.status = GameState.Status.GAME_ON;
				brd.who = currTurn;

				// Check out the results, relative to what we've seen before
				if (toMaximize && nextMove.score > bestMove.score)
				{
					bestMove.set(sr, sc, er, ec, nextMove.score);
				} else if (!toMaximize && nextMove.score < bestMove.score)
				{
					bestMove.set(sr, sc, er, ec, nextMove.score);
				}

				// Update alpha and beta. Perform pruning, if possible.
				if (toMinimize)
				{
					beta = Math.min(bestMove.score, beta);
					if (bestMove.score <= alpha || bestMove.score == -MAX_SCORE)
					{
						return;
					}
				} else
				{
					alpha = Math.max(bestMove.score, alpha);
					if (bestMove.score >= beta || bestMove.score == MAX_SCORE)
					{
						return;
					}
				}
			}
		}
	}

	/**
	 * Gets the first move on the stack
	 */
	public GameMove getMove(GameState brd, String lastMove)
	{
		int d = 15;
		double timePerTurn;
		double timeSpent = 0;
		double nextLevel = 0;

		
		if (brd.numMoves < 10) {
			d = 7;
			timePerTurn = timeRemaining / 100;
		} else
		{
			timePerTurn = timeRemaining / 10;
		}

		if (timeRemaining < 60000)
		{
			d = 7;
			timePerTurn = timeRemaining / 100;
		}

		for (int i = 0; i < d; i++)
		{
			depthLimit = i;

			double startTime = System.currentTimeMillis();
			alphaBeta((BreakthroughState) brd, 0, Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY);
			double endTime = System.currentTimeMillis();
			double duration = endTime - startTime;

			
			timeSpent += duration;
			timeRemaining -= duration;
			nextLevel = timeSpent + nextSearch(i+1);


			if (nextLevel  > timePerTurn || nextLevel > timeRemaining)
			{
				System.out.println(mvStack[0].score);
				return mvStack[0];
			}
		}

		System.out.println(mvStack[0].score);
		return mvStack[0];
	}
	
	public double nextSearch(int d) {
		double time = (.0055 * Math.pow(Math.E, 1.6375*d));
		return time;
	}
	
	public void endGame(int result) {
		timeRemaining = 420000;
	}

	public static char[] toChars(String x)
	{
		char[] res = new char[x.length()];
		for (int i = 0; i < x.length(); i++)
			res[i] = x.charAt(i);
		return res;
	}

	public static void main(String[] args)
	{
		int depth = 3;
		GamePlayer p = new AlphaBetaBreakthroughPlayer("AB BT", depth);
		p.compete(args);
	}
}
